package org.example.algorithm.stack;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 * 输入：abc3[cd]xyz
 * 输出：abccdcdcdxyz
 */
public class DecodeStringSolution {
    public static void main(String[] args) {
        DecodeStringSolution solution = new DecodeStringSolution();
        String s = "abc3[cd]xyz";
        String ans = solution.decodeString(s);
        System.out.println(ans);
    }

    public String decodeString(String s) {
        int len = s.length();
        if (len == 0) {
            return s;
        }
        Deque<Character> stack = new ArrayDeque<>();
        int cur = 0;
        StringBuilder sb = new StringBuilder();
        while (cur < len) {
            if (s.charAt(cur) != ']') {
                stack.push(s.charAt(cur));
            } else {
                StringBuilder temp = new StringBuilder();
                while (!stack.isEmpty() && stack.peek() != '[') {
                    temp.insert(0, stack.pop());
                }
                stack.pop();
                String tempStr = temp.toString();
                int base = 1;
                int sum = 0;
                while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
                    int num = stack.pop() - '0';
                    sum = num * base + sum;
                    base = base * 10;
                }
                for (int i=0;i<sum;i++) {
                    for (int j=0;j<tempStr.length();j++) {
                        stack.push(tempStr.charAt(j));
                    }
                }
            }
            cur++;
        }
        while (!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
        return sb.toString();
    }
}
